module Rdpexpr

open System

// 文法 
// <expr> ::= <term> { <addop> <term> }
// <term> ::= <factor> { <mulop> <factor> }
// <factor> ::= <number> | "(" <expr> ")"
// <number> ::= <digit> { <digit> }
// <addop> ::= "+" | "-"
// <mulop> ::= "*" | "/"
// <digit> ::= "0" | "1" | ... | "9"
// 每个文法的选择分支 ，都是确定的，所以可以确定性分析，无需回溯
// 注意：下面的程序没有对空格进行处理

//抽象语法树类型
type Expr =
    | Number of int
    | Add of Expr * Expr
    | Sub of Expr * Expr
    | Mul of Expr * Expr
    | Div of Expr * Expr

//解析表达式 expr
let rec parseExpr tokens =
    let left, remaining = parseTerm tokens

    match remaining with
    | '+' :: rest ->
        let right, newRemaining = parseTerm rest
        (Add(left, right), newRemaining)
    | '-' :: rest ->
        let right, newRemaining = parseTerm rest
        (Sub(left, right), newRemaining)
    | _ -> left, remaining

//解析项 term
and parseTerm tokens =
    let left, remaining = parseFactor tokens

    match remaining with
    | '*' :: rest ->
        let right, newRemaining = parseFactor rest
        (Mul(left, right), newRemaining)
    | '/' :: rest ->
        let right, newRemaining = parseFactor rest
        (Div(left, right), newRemaining)
    | _ -> left, remaining

//解析因子 factor
and parseFactor tokens =
    match tokens with
    | [] -> failwith "Unexpected end of input"
    | '(' :: rest ->
        let expr, remaining = parseExpr rest

        match remaining with
        | ')' :: newRemaining -> expr, newRemaining
        | ' ' :: newRemaining -> parseFactor newRemaining 
        | _ -> failwith "Missing closing parenthesis"
    | c :: rest when Char.IsDigit c ->
        let value, _ =
            let rec loop i acc =
                match List.tryItem i tokens with
                | Some c when Char.IsDigit c -> loop (i + 1) (acc * 10 + int (string c))
                | _ -> acc, i

            loop 0 0

        (Number value), (Seq.skipWhile Char.IsDigit tokens |> Seq.toList)
    | _ -> failwith "Unexpected token"


let rec evaluate expr =
    match expr with
    | Number n -> n
    | Add(left, right) -> evaluate left + evaluate right
    | Sub(left, right) -> evaluate left - evaluate right
    | Mul(left, right) -> evaluate left * evaluate right
    | Div(left, right) -> evaluate left / evaluate right


let input = "(2+33)*(4-5)"
let tokens = Seq.toList input
let expr, remaining = parseExpr tokens

if remaining <> [] then
    failwith "Last Unexpected tokens"

printfn "%A" expr
let result = evaluate expr
printfn "%d" result
